package com.breeze.leetcode.middle;

/**
 * @link <a href="https://leetcode.cn/problems/unique-paths-ii">63. 不同路径 II</a>
 */
public class T63UniquePathsII {
    /**
     * 1. 判断下一格是否可以走，能哦组
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        obstacleGrid[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        int iMax = obstacleGrid.length - 1;
        int jMax = obstacleGrid[0].length - 1;
        for (int i = 0; i <= iMax; i++) {
            for (int j = 0; j <= jMax; j++) {
                // 初始位置，直接跳过
                if (i == 0 && j == 0) {
                    continue;
                }
                // 如果当前位置是障碍，则设置为0
                if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                    continue;
                }

                if (i > 0 && j > 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                } else if (i == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i][j - 1];
                } else {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j];
                }
            }
        }

        return obstacleGrid[iMax][jMax];
    }
}
